package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class t20210314 {

    private static final int[][] dist = new int[][]{
            new int[]{},
            new int[]{0, 1},
            new int[]{0, -1},
            new int[]{1, 0},
            new int[]{-1, 0}
    };

    private static int min = Integer.MAX_VALUE;

    public static int minCost(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        min = Integer.MAX_VALUE;
        boolean[][] visited = new boolean[n][m];
        dfs(grid, visited, 0, 0, n, m, 0);
        return min==Integer.MAX_VALUE ? -1 : min;
    }

    private static void dfs(int[][] grid, boolean[][] visited, int x, int y, int n, int m, int step){
        if(x >= n || y >= m || x < 0 || y < 0 || visited[x][y] || step >= min) return;
        if(isLegal(grid, x, y, visited)){
            min = step;
        }else{
            for(int i = 1; i <= 4; i++){
                visited[x][y] = true;
                if(i != grid[x][y]) dfs(grid, visited, x+dist[i][0], y+dist[i][1], n, m, step+1);
                else dfs(grid, visited, x+dist[i][0], y+dist[i][1], n, m, step);
                visited[x][y] = false;
            }
        }


    }

    private static int getMaxRecircle(String s){
        Map<Character, Integer> map = new HashMap<>();
        for(char c : s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }
        boolean hasOne = false;
        int res = 0;
        for(Map.Entry<Character, Integer> e : map.entrySet()){
            if(e.getValue() % 2 == 0){
                res += e.getValue();
            }else{
                hasOne = true;
                res += e.getValue()-1;
            }
        }
        return hasOne ? res+1 : res;
    }

    private static boolean isLegal(int[][] grid, int x, int y, boolean[][] visited){
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] tmp = new boolean[n][m];
        for(int i = 0; i < n; i++){
            System.arraycopy(visited[i], 0, tmp[i], 0, m);
        }
        while(x < n && y < m && x>= 0 && y >= 0 && !tmp[x][y]){
            if(x == n-1 && y == m-1) return true;
            tmp[x][y] = true;
            int tx = x;
            x = x + dist[grid[x][y]][0];
            y = y + dist[grid[tx][y]][1];

        }
        return false;
    }

    public static void main(String[] args){
        int[][] a = new int[][]{
//                new int[]{1,1,1,1},
//                new int[]{2,2,2,2},
//                new int[]{1,1,1,1},
//                new int[]{2,2,2,2},

                new int[]{1,2},
                new int[]{4,3},
        };
        System.out.println(minCost(a));


    }
}
